/**
 * Класс, предназначенный для сериализации и десериализации объектов типа Tree.
 * В качестве формата хранения выбран XML, закодированный в Base64
 */

#ifndef _TREESERIALIZER_H
#define	_TREESERIALIZER_H

#include <string>
#include <map>
#include "common/Base64.h"
#include "common/ObjectSerializer.h"
#include "common/XmlSerializer.h"
#include "common/ParseException.h"
#include "common/XmlStringTranscoder.h"
#include "Tree.h"
#include "conf.h"

namespace etu {
namespace tree {

XERCES_CPP_NAMESPACE_USE

template <typename T>
class TreeSerializer : public common::ObjectSerializer<Tree<T> *>,
        public common::XmlSerializer {
    
public:
    TreeSerializer() {}
    TreeSerializer(const TreeSerializer& orig) {}
    virtual ~TreeSerializer() {}

    /*
     * Сериализованное дерево в XML-представлении выглядит так:
     * <code>
     * <tree root_uid="val : Uid">
     *  <node uid="val : Ui>">
     *   <value>
     *    serialized_value : string
     *   </value>
     *   <parent uid="val : Uid"/>
     *   <parent uid="val : Uid"/>
     *   ...
     *   <child uid="val : Uid"/>
     *   <child uid="val : Uid/>
     *   ...
     *  </node>
     *  ...
     * </tree>
     * </code>
     *
     * <br/>
     * В ближайшем приближении алгоритм сериализации выглядит так:
     * 1) Проходимся по всем узлам дерева и каждому присваем идентификатор.
     * Идентификатор корня указываем корню DOM-дерева.
     * 3) Второй раз проходим по всем узлам и добавляем их в DOM-документ.
     * Для каждого из них:
     * а) задаём дочерний DOM-узел с сериализованным значением
     * узла дерева
     * б) добавляем список дочерних DOM-узлов с идентификаторами
     * узлов-потомков данного узла дерева
     * в) добавляем список родительских DOM-узлов с идентификаторами
     * узлов-родителей данного узла дерева
     */
    
    virtual std::string serialize(Tree<T>* tree) {
        DOMDocument* doc = this->createDocument("tree");
        DOMElement* root = doc->getDocumentElement();

        if(!tree->isEmpty()) {
            std::map<T, Uid>* uids = generateUids(tree);
            Uid rootUid = getUid(tree->getRoot(), uids);
            root->setAttribute(X("root_uid"), X(rootUid));

            TreeIterator<T>* it = tree->getIterator();

            while(it->hasNext()) {
                T nextValue = it->next();
                Uid uid = getUid(nextValue, uids);
                this->appendNode(tree, doc, nextValue, uid, uids);
            }

            delete it;
            delete uids;
        }

        std::string ret = this->documentToString(doc);
        doc->release();

        return common::Base64::encode(ret);
    }

    /*
     * В ближайшем приближении алгоритм десериализации выглядит так:
     * 1) Проходимся по всем DOM-узлам и формируем следующую информацию по каждой:
     * - идентификатор
     * - значение
     * - список идентификаторов узлов-потомков
     * - список идентификаторов узлов-родителей
     * 2) Создаём пустой список узлов, пока уже добавленных в дерево
     * 3) Начиная с корня узла, отмеченного как корень дерева, рекурсивно
     * проходимся по всем узлам в таком порядке:
     * - добавляем текущий узел в дерево
     * - добавляем текущий узел в список узлов, уже добавленных в дерево
     * - проходим по всем узлам-потомкам, и если какой-нибудь из них ещё
     * не добавлен, то делаем его текущим и выполняем п. 3 для него (рекурсия)
     * - проходим по всем узлам-родителям, и если какой-нибудь из них ещё
     * не добавлен, то делаем его текущим и выполняем п. 3 для него (рекурсия)
     * - возвращаемся на уровень рекурсии выше
     */

    virtual Tree<T>* deserialize(const std::string& src) throw(common::ParseException) {
        DOMDocument* doc = this->buildDocument(common::Base64::decode(src));
        DOMElement* root = doc->getDocumentElement();
        Tree<T>* ret = new Tree<T>();

        if(!root->hasAttribute(X("root_uid"))) {
            // tree can be empty
            // throw ParseException("Root node must have the 'root_uid' attribute");
        } else {
            Uid rootUid = TreeSerializer::stringToUid(
                    XMLString::transcode(root->getAttribute(X("root_uid"))));

            ParsedTree parsedTree;

            std::list<ParsedNode *>* parsedNodes
                    = TreeSerializer::parseNodes(root);
            parsedTree.parsedNodes = parsedNodes;
            parsedTree.tree = ret;
            parsedTree.doc = doc;
            
            ParsedNode* rootNode = findNodeByUid(rootUid, parsedTree);

            ret->setRoot(rootNode->value);
            parsedTree.addedToTreeNodes.push_back(rootNode);

            TreeSerializer::addChildsToTree(rootNode, parsedTree);
            TreeSerializer::addParentsToTree(rootNode, parsedTree);

            TreeSerializer::purgeParsedNodes(parsedNodes);
        }

        return ret;
    }

private:

    /**
     * Идентификатор узла дерева
     */
    typedef long Uid;

    /**
     *
     */
    typedef struct {
        Uid uid;
        T value;
        std::list<Uid> parents;
        std::list<Uid> childs;
    } ParsedNode;

    typedef struct {
        Tree<T>* tree;
        std::list<ParsedNode *>* parsedNodes;
        std::list<ParsedNode *> addedToTreeNodes;
        DOMDocument* doc;
    } ParsedTree;

    static Uid stringToUid(const std::string& str) {
        return atol(str.c_str());
    }

    static std::map<T, Uid>* generateUids(Tree<T>* tree) {
        Uid nextUid = 1;
        std::map<T, Uid>* ret = new std::map<T, Uid>();

        TreeIterator<T>* it = tree->getIterator();

        while(it->hasNext()) {
            std::pair<T, Uid> next
                    = std::make_pair<T, Uid>(it->next(), nextUid);
            ret->insert(next);
            nextUid++;
        }

        delete it;

        return ret;
    }

    static Uid getUid(T element, const std::map<T, Uid>* uids) {
        Uid ret;
        typename std::map<T, Uid>::const_iterator it;

        for(it = uids->begin(); it != uids->end(); it++) {
            if((* it).first == element) {
                ret = (* it).second;
                break;
            }
        }

        return ret;
    }

    static void appendNode(Tree<T>* tree, DOMDocument* doc, T value, 
        Uid id, std::map<T, Uid>* uids) {

        DOMElement* node = doc->createElement(X("node"));
        std::ostringstream valueText;
        valueText << value;

        node->setAttribute(X("uid"), X(id));

        DOMElement* valueNode = doc->createElement(X("value"));
        valueNode->setTextContent(X(valueText.str()));
        node->appendChild(valueNode);

        typename std::list<T>::iterator it;
        std::list<T>* parents = tree->getParents(value);
        std::list<T>* childs = tree->getChilds(value);

        for(it = parents->begin(); it != parents->end(); it++) {
            T parent = (* it);
            DOMElement* parentNode = doc->createElement(X("parent"));
            parentNode->setAttribute(X("uid"), X(getUid(parent, uids)));

            node->appendChild(parentNode);
        }

        for(it = childs->begin(); it != childs->end(); it++) {
            T child = (* it);
            DOMElement* childNode = doc->createElement(X("child"));
            childNode->setAttribute(X("uid"), X(getUid(child, uids)));

            node->appendChild(childNode);
        }

        delete parents;
        delete childs;

        doc->getDocumentElement()->appendChild(node);
    }

    static void removeNodeByUid(Uid uid, std::list<ParsedNode *>* parsedNodes) {
        typename std::list<Uid>::iterator it;

        for(it = parsedNodes->begin(); it != parsedNodes->end(); it++) {
            ParsedNode* node = (* it);

            if(node->uid == uid) {
                parsedNodes->erase(it);
                break;
            }
        }
    }

    static void addChildsToTree(ParsedNode* parent, ParsedTree& parsedTree) {

        typename std::list<Uid>::iterator it;

        for(it = parent->childs.begin(); it != parent->childs.end(); it++) {
            Uid uid = (* it);
            ParsedNode* child = TreeSerializer::findNodeByUid(uid, parsedTree);

            if(!TreeSerializer::isNodeAddedToTree(child, parsedTree)) {
                parsedTree.tree->addChild(parent->value, child->value);
                parsedTree.addedToTreeNodes.push_back(child);

                TreeSerializer::addChildsToTree(child, parsedTree);
                TreeSerializer::addParentsToTree(child, parsedTree);
            } else {
                parsedTree.tree->addParent(child->value, parent->value);
            }
        }
    }

    static void addParentsToTree(ParsedNode* child, ParsedTree& parsedTree) {

        typename std::list<Uid>::iterator it;

        for(it = child->parents.begin(); it != child->parents.end(); it++) {
            Uid uid = (* it);
            ParsedNode* parent = TreeSerializer::findNodeByUid(uid, parsedTree);

            if(!TreeSerializer::isNodeAddedToTree(parent, parsedTree)) {
                parsedTree.tree->addParent(child->value, parent->value);
                parsedTree.addedToTreeNodes.push_back(parent);

                TreeSerializer::addChildsToTree(parent, parsedTree);
                TreeSerializer::addParentsToTree(parent, parsedTree);
            } else {
                parsedTree.tree->addChild(parent->value, child->value);
            }
        }
    }

    static void purgeParsedNodes(std::list<ParsedNode *>* parsedNodes) {
        typename std::list<ParsedNode *>::iterator it = parsedNodes->begin();

        while(it != parsedNodes->end()) {
            ParsedNode* node = (* it);
            it++;
            delete node;
        }
    }

    static bool isNodeAddedToTree(ParsedNode* node, const ParsedTree& parsedTree) {
        bool ret = false;
        typename std::list<ParsedNode *>::iterator it;
        std::list<ParsedNode *> addedToTreeNodes = parsedTree.addedToTreeNodes;

        for(it = addedToTreeNodes.begin(); it != addedToTreeNodes.end(); it++) {
            ParsedNode* parsedNode = (* it);

            if(parsedNode == node) {
                ret = true;
                break;
            }
        }

        return ret;
    }

    static ParsedNode* findNodeByUid(Uid uid, const ParsedTree& parsedTree) {
        ParsedNode* ret = NULL;
        typename std::list<ParsedNode *>::iterator it;
        std::list<ParsedNode *>* parsedNodes = parsedTree.parsedNodes;

        for(it = parsedNodes->begin(); it != parsedNodes->end(); it++) {
            ParsedNode* node = (* it);

            if(node->uid == uid) {
                ret = node;
                break;
            }
        }

        return ret;
    }

    static std::list<ParsedNode *>* parseNodes(DOMElement* root) 
        throw(common::ParseException) {
        
        std::list<ParsedNode *>* ret = new std::list<ParsedNode *>();

        DOMNodeList* nodes = root->getChildNodes();
        const XMLSize_t nodesCount = nodes->getLength();

        for(XMLSize_t i = 0; i < nodesCount; i++) {
            DOMNode* node = nodes->item(i);

            if((node->getNodeType() != 0)
                    && node->getNodeType() == DOMNode::ELEMENT_NODE) {

                DOMElement* nodeElement = dynamic_cast<DOMElement *>(node);
                std::string nodeName
                        = XMLString::transcode(nodeElement->getNodeName());

                if(nodeName == "node") {
                    ret->push_back(parseNode(nodeElement));
                }
            }
        }

        return ret;
    }

    static ParsedNode* parseNode(DOMElement* node) throw(common::ParseException) {
        if(!node->hasAttribute(X("uid"))) {
            throw common::ParseException("Корень не содержит атрибут 'uid'");
        }

        ParsedNode* ret = new ParsedNode();
        ret->uid = stringToUid(
                XMLString::transcode(node->getAttribute(X("uid"))));
        ret->value = defaultParameterValue();
        bool hasValueNode = false;

        DOMNodeList* nodes = node->getChildNodes();
        const XMLSize_t nodesCount = nodes->getLength();

        for(XMLSize_t i = 0; i < nodesCount; i++) {
            DOMNode* node = nodes->item(i);

            if((node->getNodeType() != 0)
                    && node->getNodeType() == DOMNode::ELEMENT_NODE) {
                DOMElement* nodeElement = dynamic_cast<DOMElement *>(node);
                std::string nodeName
                        = XMLString::transcode(nodeElement->getNodeName());

                if(nodeName == "value") {
                    std::istringstream iss;
                    iss.str(XMLString::transcode(nodeElement->getTextContent()));
                    iss >> ret->value;
                    hasValueNode = true;
                } else if(nodeName == "parent") {
                    Uid uid = stringToUid(XMLString::transcode(
                            nodeElement->getAttribute(X("uid"))));
                    ret->parents.push_back(uid);
                } else if(nodeName == "child") {
                    Uid uid = stringToUid(XMLString::transcode(
                            nodeElement->getAttribute(X("uid"))));
                    ret->childs.push_back(uid);
                }
            }
        }

        if(!hasValueNode) {
            delete ret;
            throw new common::ParseException("Tree node must have 'value' node");
        }

        return ret;
    }

    static T defaultParameterValue() {
        return T();
    }
};

}
}

#endif	/* _TREESERIALIZER_H */

